package com.fanshuai.algorithms.divide;

/**
 * 金块问题
 * 老板有一袋金块(共n块)，最优秀的雇员得到其中最重的一块，最差的雇员得到其中最轻的一块。
 * 假设有一台比较重量的仪器，我们希望用最少的比较次数找出最重的金块。
 */
public class Gold {
    /**
     * 金块问题  分治法解决
     * 将n个金块分成两堆，每对n/2个金块。分别求两堆金块的最大值max1, max2，最终结果为：max(max1, max2)
     * 递归的对金块拆分，当金块只剩下一块时，返回此金块的重量
     * @param golds
     * @return
     */
    public static double findMax(double[] golds) {
        return findMax(golds, 0, golds.length - 1);
    }

    private static double findMax(double[] golds, int left, int right) {
        if (left == right) {
            return golds[left];
        }

        int mid = (left + right) / 2;
        double maxLeft = findMax(golds, left, mid);
        double maxRight = findMax(golds, mid + 1, right);

        return Math.max(maxLeft, maxRight);
    }

    public static void main(String[] args) {
        double[] a = {4.5, 2.3, 3.4, 1.2, 6.7, 9.8, 5, 6};
        System.out.println(findMax(a));
    }
}
